package com.example.dynamicprogramming42.practice;

/**
 * @description 课后练习，如何求出这个序列中的最长递增子序列长度？
 * 比如 2, 9, 3, 6, 5, 1, 7 这样一组数字序列，它的最长递增子序列就是 2, 3, 5, 7，所以最长递增子序列的长度是 4。
 * @auther lijiewei
 * @date 2022/5/16 16:26
 */
public class DynamicProgrammingPractice {



    /**
     * 状态转移表法求最长递增子序列长度
     * 状态转移方程：
     * 如果 a[j]<a[i]: max_son=max(maxDist[j][j-1]+1, maxDist[i][j-1])
     * 如果 a[j]>=a[i]: max_son=maxDist[i][j-1]
     * @param a 数组a
     * @param n 数组a的长度
     * @return
     * @author lijiewei
     * @date   2022/5/17 14:37
     */
    public int getMaxSonLength(int[] a, int n) {
        //二维状态表，比较完a[i],b[j]后的最长递增子序列长度
        int[][] maxDist = new int[n][n];

        //初始化第0行
        for (int j = 0; j < n; j++) {
            maxDist[0][j] = 1;
        }

        //初始化第0列
        for (int i = 0; i < n; i++) {
            if (a[i] > a[0]) {
                maxDist[i][0] = 2;
            } else {
                maxDist[i][0] = 1;
            }
        }


        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                if (j<i && a[j]<a[i]) {
                    maxDist[i][j] = max(maxDist[j][j]+1, maxDist[i][j-1]);
                } else {
                    maxDist[i][j] = maxDist[i][j-1];
                }
            }
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            result = maxDist[i][n-1] > result ? maxDist[i][n-1] : result;
        }

        return result;
    }

    /**
     * 三个数求最大值
     * @param x
     * @param y
     * @return
     * @author lijiewei
     * @date   2022/5/17 14:34
     */
    private int max(int x, int y) {
        return x>y ? x : y;
    }

    /**
     * 状态转移表法求最长递增子序列长度
     * 状态转移方程：
     * 如果 a[j]<a[i]: max_son=max(maxDist(j, j-1)+1, maxDist(i, j-1))
     * 如果 a[j]>=a[i]: max_son=maxDist(i, j-1)
     * @param a 数组a
     * @param n 数组a的长度
     * @return
     * @author lijiewei
     * @date   2022/5/17 14:37
     */
    public int getMaxSonLength2(int[] a, int n) {
        this.a = a;
        this.mem = new int[n][n];
        maxDist(n-1, n-1);
        int result = 0;
        for (int i = 0; i < n; i++) {
            result = mem[i][n-1] > result ? mem[i][n-1] : result;
        }

        return result;

    }

    private int[] a;
    private int[][] mem;

    private int maxDist(int i, int j) {
        //第0行
        if (i==0) {
            mem[i][j] = 1;
            return mem[i][j];
        }

        //第0列
        if (j==0) {
            if (a[i] > a[j]) {
                mem[i][j] = 2;
            } else {
                mem[i][j] = 1;
            }
            return mem[i][j];
        }

        if (mem[i][j]>0) {
            return mem[i][j];
        }
        if (j<i && a[j]<a[i]) {
            mem[i][j]=max(maxDist(j, j-1)+1, maxDist(i, j-1));
        } else {
            mem[i][j]=maxDist(i, j-1);
        }
        return mem[i][j];
    }

}
